#ifndef LFUCACHE_H
#define LFUCACHE_H

#include "../cachePolicy.h"
#include <memory>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <vector>

namespace Cache {
using namespace std;

template <typename Key, typename Value> class LFUCache;

template <typename Key, typename Value> class FreqList {
private:
    struct Node {
        int freq;              // 频率
        Key key;               // 键值
        Value value;           // 值
        shared_ptr<Node> pre;  // 上一结点
        shared_ptr<Node> next; // 下一节点

        Node() : freq(1), pre(nullptr), next(nullptr) {}
        Node(Key k, Value v) : freq(1), key(k), value(v), pre(nullptr), next(nullptr) {
            // cout << "Successful FreqList Node construct with (key, value)" << endl;
        }
    };
    using NodePtr = shared_ptr<Node>;

    int freq_;     // 访问频率
    NodePtr head_; // 虚拟头节点
    NodePtr tail_; // 虚拟尾节点

public:
    explicit FreqList(int n) : freq_(n) {
        head_ = make_shared<Node>();
        tail_ = make_shared<Node>();
        head_->next = tail_;
        tail_->pre = head_;

        // cout << "Successful FreqList construct" << endl;
    }

    bool isEmpty() {
        return head_->next == tail_;
    }

    void addNode(NodePtr n) {
        if (!n || !head_ || !tail_)
            return;

        n->pre = tail_->pre;
        n->next = tail_;
        tail_->pre->next = n;
        tail_->pre = n;
    }

    void removeNode(NodePtr n) {
        if (!n || !head_ || !tail_)
            return;
        if (!n->pre || !n->next)
            return;
        n->pre->next = n->next;
        n->next->pre = n->pre;
        n->pre = nullptr;
        n->next = nullptr;
    }

    NodePtr getFirstNode() const {
        return head_->next;
    }

    friend class LFUCache<Key, Value>;
};

template <typename Key, typename Value> class LFUCache : public cachePolicy<Key, Value> {

public:
    using Node = typename FreqList<Key, Value>::Node;
    using NodePtr = shared_ptr<Node>;
    using NodeMap = unordered_map<Key, NodePtr>;
    LFUCache(size_t capacity, int maxAvgNum = 10)
        : capacity_(capacity), maxAvgNum_(maxAvgNum), minFreq_(INT32_MAX), curAvgNum_(0), curTotalNum_(0) {};

    ~LFUCache() override = default;

    void put(Key k, Value v) override {
        if (capacity_ == 0)
            return;
        lock_guard<mutex> lock(mutex_);
        auto it = nodeMap_.find(k);
        if (it != nodeMap_.end()) {
            // 重置value值
            it->second->value = v;
            getInternal(it->second, v);
            return;
        }
        putInternal(k, v);
    }

    bool get(Key k, Value &v) override {
        lock_guard<mutex> lock(mutex_);
        auto it = nodeMap_.find(k);
        if (it != nodeMap_.end()) {
            getInternal(it->second, v);
            return true;
        }
        return false;
    }

    Value get(Key k) override {
        Value value{};
        get(k, value);
        return value;
    }

    // 清空缓存,回收资源
    void purge() {
        nodeMap_.clear();
        freqToFreqList_.clear();
    }

private:
    void putInternal(Key k, Value v) { // 添加缓存
        if (nodeMap_.size() == capacity_) {
            // 缓存满，删除最不常访问的节点并更新平均和总访问频次
            kickOut();
        }
        // 创建新节点，更新访问频次
        NodePtr node = make_shared<Node>(k, v);
        nodeMap_[k] = node;
        addToFreqList(node);
        addFreqNum();
        minFreq_ = min(minFreq_, 1);
    }
    void getInternal(NodePtr n, Value &v) { // 获取缓存
        // 找到后从低访问频次链表删除，添加到+1的访问频次链表中
        // 访问频次+1 返回v值
        v = n->value;
        removeFromFreqList(n);
        n->freq++;
        addToFreqList(n);
        // n的访问频次=minFreq+1且前驱链表空
        // 说明 freqToFreqList[node->freq - 1] 因为
        // 移动了 n 变为空链表
        // 需要修改最小访问频次
        if (n->freq - 1 == minFreq_ && freqToFreqList_[n->freq - 1]->isEmpty())
            minFreq_++;
        addFreqNum();
    }

    void kickOut() { // 删除最不常访问的节点
        NodePtr node = freqToFreqList_[minFreq_]->getFirstNode();
        removeFromFreqList(node);
        nodeMap_.erase(node->key);
        decreaseFreqNum(node->freq);
    }

    void removeFromFreqList(NodePtr n) { // 从当前频次链表中删除节点
        if (!n)
            return;
        freqToFreqList_[n->freq]->removeNode(n);
    }

    void addToFreqList(NodePtr n) {
        if (!n)
            return;
        auto freq = n->freq;
        if (freqToFreqList_.find(freq) == freqToFreqList_.end())
            freqToFreqList_[freq] = new FreqList<Key, Value>(freq); // 不存在，创建

        freqToFreqList_[freq]->addNode(n);
    }

    void addFreqNum() { // 增加平均访问等频率
        curTotalNum_++;
        if (nodeMap_.empty())
            curAvgNum_ = 0;
        else
            curAvgNum_ = curTotalNum_ / nodeMap_.size();
        if (curAvgNum_ > maxAvgNum_)
            handleOverMaxAvgNum();
    }

    void handleOverMaxAvgNum() { // 处理当前平均访问频率超过上限的情况
        if (nodeMap_.empty())
            return;
        for (auto it = nodeMap_.begin(); it != nodeMap_.end(); it++) {
            NodePtr node = it->second;
            if (!node)
                continue;
            // 从当前链表中移除
            removeFromFreqList(node);
            node->freq -= (maxAvgNum_ / 2);

            if (node->freq < 1)
                node->freq = 1;

            addToFreqList(node);
        }
        updateMinFreq();
    }

    void decreaseFreqNum(int freq) { // 减少平均访问频次和总访问频次
        curTotalNum_ -= freq;
        if (nodeMap_.empty())
            curAvgNum_ = 0;
        else
            curAvgNum_ = curTotalNum_ / nodeMap_.size();
    }

    void updateMinFreq() {
        minFreq_ = INT32_MAX;
        for (const auto &pair : freqToFreqList_)
            if (pair.second && !pair.second->isEmpty())
                minFreq_ = min(minFreq_, pair.first);

        if (minFreq_ == INT32_MAX)
            minFreq_ = 1;
    }

private:
    size_t capacity_; // 缓存容量
    int minFreq_;     // 最小访问频次(用于找到最小访问频次结点)
    int maxAvgNum_;   // 最大平均访问频次
    int curAvgNum_;   // 当前平均访问频次
    int curTotalNum_; // 当前访问所有缓存次数总数
    mutex mutex_;     // 互斥锁
    NodeMap nodeMap_;
    unordered_map<int, FreqList<Key, Value> *> freqToFreqList_; // 访问次数到该频次链表的映射
};

template <typename Key, typename Value> class HashLFUCache : public cachePolicy<Key, Value> {
public:
    HashLFUCache(size_t capacity, int sliceNum, int maxAvgNum = 10)
        : capacity_(capacity), sliceNum_(sliceNum > 0 ? sliceNum : thread::hardware_concurrency()) {
        size_t sliceSize = (capacity_ + sliceNum_ - 1) / sliceNum_;
        for (int i = 0; i < sliceSize; i++)
            lfuSilceCaches_.emplace_back(make_unique<LFUCache<Key, Value>>(sliceSize, maxAvgNum));
        // cout << "Successful HashLFUCache construct" << endl;
    }

    void put(Key k, Value v) override {
        size_t sliceIdx = Hash(k) % sliceNum_;
        return lfuSilceCaches_[sliceIdx]->put(k, v);
    }

    bool get(Key k, Value &v) override {
        size_t sliceIdx = Hash(k) % sliceNum_;
        return lfuSilceCaches_[sliceIdx]->get(k, v);
    }

    Value get(Key k) override {
        Value value{};
        get(k, value);
        return value;
    }

    void purge() {
        for (auto &sliceCache : lfuSilceCaches_)
            sliceCache->purge();
    }

private:
    size_t Hash(Key k) {
        return hash<Key>{}(k);
    }

    size_t capacity_;                                         // 总容量
    int sliceNum_;                                            // 分片数
    vector<unique_ptr<LFUCache<Key, Value>>> lfuSilceCaches_; // lfu分片容器
};
} // namespace Cache

#endif